package com.shm.leetcode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.TreeMap;

/**
 * 1438. 绝对差不超过限制的最长连续子数组
 * 给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。
 *
 * 如果不存在满足条件的子数组，则返回 0 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [8,2,4,7], limit = 4
 * 输出：2
 * 解释：所有子数组如下：
 * [8] 最大绝对差 |8-8| = 0 <= 4.
 * [8,2] 最大绝对差 |8-2| = 6 > 4.
 * [8,2,4] 最大绝对差 |8-2| = 6 > 4.
 * [8,2,4,7] 最大绝对差 |8-2| = 6 > 4.
 * [2] 最大绝对差 |2-2| = 0 <= 4.
 * [2,4] 最大绝对差 |2-4| = 2 <= 4.
 * [2,4,7] 最大绝对差 |2-7| = 5 > 4.
 * [4] 最大绝对差 |4-4| = 0 <= 4.
 * [4,7] 最大绝对差 |4-7| = 3 <= 4.
 * [7] 最大绝对差 |7-7| = 0 <= 4.
 * 因此，满足题意的最长子数组的长度为 2 。
 * 示例 2：
 *
 * 输入：nums = [10,1,2,4,7,2], limit = 5
 * 输出：4
 * 解释：满足题意的最长子数组是 [2,4,7,2]，其最大绝对差 |2-7| = 5 <= 5 。
 * 示例 3：
 *
 * 输入：nums = [4,2,2,2,4,4,2,2], limit = 0
 * 输出：3
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 10^5
 * 1 <= nums[i] <= 10^9
 * 0 <= limit <= 10^9
 * @author SHM
 */
public class LongestSubarray {
    /**
     * 方法一：滑动窗口 + 有序集合
     * 思路和解法
     *
     * 我们可以枚举每一个位置作为右端点，找到其对应的最靠左的左端点，满足区间中最大值与最小值的差不超过 \textit{limit}limit。
     *
     * 注意到随着右端点向右移动，左端点也将向右移动，于是我们可以使用滑动窗口解决本题。
     *
     * 为了方便统计当前窗口内的最大值与最小值，我们可以使用平衡树：
     *
     * 语言自带的红黑树，例如 \texttt{C++}C++ 中的 \texttt{std::multiset}std::multiset，\texttt{Java}Java 中的 \texttt{TreeMap}TreeMap；
     *
     * 第三方的平衡树库，例如 \texttt{Python}Python 中的 \texttt{sortedcontainers}sortedcontainers（事实上，这个库的底层实现并不是平衡树，但各种操作的时间复杂度仍然很优秀）；
     *
     * 手写 \texttt{Treap}Treap 一类的平衡树，例如下面的 \texttt{Golang}Golang 代码。
     *
     * 来维护窗口内元素构成的有序集合。
     * 复杂度分析
     *
     * 时间复杂度：O(n \log n)O(nlogn)，其中 nn 是数组长度。向有序集合中添加或删除元素都是 O(\log n)O(logn) 的时间复杂度。每个元素最多被添加与删除一次。
     *
     * 空间复杂度：O(n)O(n)，其中 nn 是数组长度。最坏情况下有序集合将和原数组等大。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/solution/jue-dui-chai-bu-chao-guo-xian-zhi-de-zui-5bki/
     * @param nums
     * @param limit
     * @return
     */
    public int longestSubarray(int[] nums, int limit) {
        int n = nums.length;
        int left = 0,right= 0;
        TreeMap<Integer,Integer> map = new TreeMap<>();
        int ans = 0;
        while(right<n){
            map.put(nums[right],map.getOrDefault(nums[right],0)+1);
            while(map.lastKey()-map.firstKey()>limit){
                map.put(nums[left],map.get(nums[left])-1);
                if(map.get(nums[left])==0){
                    map.remove(nums[left]);
                }
                left++;
            }
            right++;
            ans =Math.max(ans,right-left);
        }
        return ans;
    }

    /**
     * 方法二：滑动窗口 + 单调队列
     * 思路和解法
     *
     * 在方法一中，我们仅需要统计当前窗口内的最大值与最小值，因此我们也可以分别使用两个单调队列解决本题。
     *
     * 在实际代码中，我们使用一个单调递增的队列 \textit{queMin}queMin 维护最小值，一个单调递减的队列 \textit{queMax}queMax 维护最大值。这样我们只需要计算两个队列的队首的差值，即可知道当前窗口是否满足条件。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n)O(n)，其中 nn 是数组长度。我们最多遍历该数组两次，两个单调队列入队出队次数也均为 O(n)O(n)。
     *
     * 空间复杂度：O(n)O(n)，其中 nn 是数组长度。最坏情况下单调队列将和原数组等大。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/solution/jue-dui-chai-bu-chao-guo-xian-zhi-de-zui-5bki/
     * @param nums
     * @param limit
     * @return
     */
    public int longestSubarray_2(int[] nums, int limit) {
        int n = nums.length;
        int left = 0, right = 0;
        int ans = 0;
        Deque<Integer> dequeMax = new LinkedList<>();
        Deque<Integer> dequeMin = new LinkedList<>();

        while (right < n) {
            while (!dequeMax.isEmpty()&&dequeMax.peekLast()<nums[right]){
                dequeMax.pollLast();
            }
            while (!dequeMin.isEmpty()&&dequeMin.peekLast()>nums[right]){
                dequeMin.pollLast();
            }
            dequeMax.offerLast(nums[right]);
            dequeMin.offerLast(nums[right]);
            while (!dequeMax.isEmpty()&&!dequeMin.isEmpty()&&dequeMax.peekFirst()-dequeMin.peekFirst()>limit){
                if(nums[left]==dequeMax.peekFirst()){
                    dequeMax.pollFirst();
                }
                if(nums[left]==dequeMin.peekFirst()){
                    dequeMin.pollFirst();
                }
                left++;
            }

            right++;
            ans = Math.max(ans,right-left);
        }
        return ans;
    }
}
